package com.zh.index.btree.model;

import java.util.Iterator;

/**
 * Created by Administrator on 2021/7/24.
 * 叶子节点
 */
public  class LeafNode<T extends Comparable> extends Node<T>{


    private DataNode<T> headDataNode;

    public LeafNode<T> addDataNode(DataNode<T> node) {
        initDataNode(node);
        if (null == headDataNode) {
            this.headDataNode = node;
            this.t = node.t;
        } else {
            DataNode<T> leftNode = findLeftDataNode(node.t);
            addRightDataNode(leftNode, node);
        }
        increase();
        return this;
    }

    /**
     * 删除节点
     * @param node
     */
    public void delDataNode(DataNode<T> node) {
        if (this.headDataNode == node) {
            if (size() > 1) {
                this.headDataNode = node.nextDataNode;
                changeHead(node.t);
            }
            else this.headDataNode = null;
        }
        node.delete();
        decrement();
    }

    /**
     * 再 thisNode 节点的右边增加 node 节点
     * @param thisNode
     * @param node
     */
    protected void addRightDataNode(DataNode thisNode, DataNode<T> node) {
        // 在最左边增加节点
        if (null == thisNode) {
            this.headDataNode.addLeftNode(node);
            this.headDataNode = node;
            this.t = node.t;
            return;
        }
        thisNode.addRightDataNode(node);
    }

    @Override
    public DataNode<T> findLeftDataNode(T t) {
        Iterator<DataNode> iterator = iterator();
        DataNode node = null;
        while (iterator.hasNext()) {
            node = iterator.next();
            if (node.compareTo(t) > 0)
                return node.preDataNode;
        }
        return node;
    }

    @Override
    public BranchNode<T> divisionNode(int degree) {
        if (size() < degree)
            return null;
        int center = degree >> 1;
        int i = 0;
        LeafNode<T> newLeafNode = new LeafNode<>();
        Itr iterator = (Itr) iterator();

        while (iterator.hasNext()) {
            DataNode<T> temp = iterator.next();
            if (i > center) {
                newLeafNode.initDataNode(temp);
            } else if (i == center) {
                newLeafNode.initDataNode(temp);
                newLeafNode.headDataNode = temp;
                newLeafNode.t = temp.t;
            }
            i++;
        }
        this.setSize(center);
        newLeafNode.setSize(degree - center);

        // 当前节点为最高节点
        if (isRootNode()) {
            belongInnerNode = new BranchInnerNode<>(this, newLeafNode);
            BranchNode<T> root = new BranchNode<>(belongInnerNode);
            return root;
        }
        BranchInnerNode belongInnerNode = this.belongInnerNode;
        BranchInnerNode newInner =  new BranchInnerNode<>(this, newLeafNode);
        // 非最右边节点
        if (belongInnerNode.t.compareTo(newInner.t) > 0) {
            belongInnerNode.addLeftInnerNode(newInner);
        } else {
            belongInnerNode.addRightInnerNode(newInner);
        }
        return getParentNode().divisionNode(degree);
    }

    public Node<T> brorrowOrMergeNode(int minSize) {
        if (size() >= minSize)
            return null;
        BranchInnerNode innerNode = this.belongInnerNode;
        if (null == innerNode)
            return null;
        boolean flag = false;
        if (this == innerNode.rightChildrenNode)
            flag = borrowForLeft((LeafNode) innerNode.leftChildrenNode, minSize);
        else {
            if (null != innerNode.preInnerNode)
                flag = borrowForLeft((LeafNode) innerNode.preInnerNode.leftChildrenNode, minSize);
            if (!flag) {
                if (null == innerNode.nextInnerNode)
                    flag = borrowForRight((LeafNode<T>) innerNode.rightChildrenNode, minSize);
                else flag = borrowForRight((LeafNode<T>) innerNode.nextInnerNode.leftChildrenNode, minSize);
            }
        }

        // 成功借到
        if (flag)
            return null;
        return mergeNode(minSize);
    }

    /**
     * 合并操作
     * @param minSize
     * @return
     */
    private Node<T> mergeNode(int minSize) {
        LeafNode<T> left = getPreLeafNode();
        if (null != left)
            mergeLeftNode(left);
        else {
            mergeRightNode(getNextLeafNode());
        }


        return null;
    }

    private void mergeLeftNode(LeafNode<T> node) {

    }

    /**
     * 将右边的节点合并到本节点
     * @param node
     */
    private void mergeRightNode(LeafNode<T> node) {
        if (null == this.headDataNode) {
            this.headDataNode = node.headDataNode;
            this.changeHead(this.headDataNode.t);
        }
        DataNode<T> temp = this.headDataNode;
        Iterator iterator = iterator();
        while (iterator.hasNext()) temp = (DataNode<T>) iterator.next();
        if (temp != node.headDataNode) {
            temp.nextDataNode = node.headDataNode;
            if (null != node.headDataNode)
                node.headDataNode.preDataNode = temp;
        }
        iterator = node.iterator();
        while (iterator.hasNext()) {
            this.increase();
            DataNode<T> dn = (DataNode<T>) iterator.next();
            dn.setParentNode(this);
        }
    }

    /**
     * 尝试从左借
     * @return
     */
    private boolean borrowForLeft(LeafNode<T> lender, int minSize) {
        if (lender.size() <= minSize)
            return false;
        DataNode<T> newH = null;
        if (null == this.headDataNode) {
            Iterator iterator = lender.iterator();
            while (iterator.hasNext()) newH = (DataNode<T>) iterator.next();
        } else {
            newH = this.headDataNode.preDataNode;
        }
        lender.decrement();
        this.headDataNode = newH;
        this.changeHead(newH.t);
        this.increase();
        return true;
    }

    private boolean borrowForRight(LeafNode<T> lender, int minSize) {
        if (lender.size() <= minSize)
            return false;
        this.increase();
        if (null == this.headDataNode) {
            this.headDataNode = lender.headDataNode;
            this.changeHead(this.headDataNode.t);
        }
        lender.headDataNode = lender.headDataNode.nextDataNode;
        lender.decrement();
        lender.changeHead(lender.headDataNode.t);
        return true;
    }

    protected void initDataNode(DataNode node) {
        node.setParentNode(this);
    }

    private LeafNode<T> getPreLeafNode() {
        if (this == this.belongInnerNode.branchNode.headInnerNode.leftChildrenNode)
            return null;
        if (this == this.belongInnerNode.rightChildrenNode)
            return (LeafNode<T>)this.belongInnerNode.leftChildrenNode;
        return (LeafNode<T>)this.belongInnerNode.preInnerNode.leftChildrenNode;
    }

    private LeafNode<T> getNextLeafNode() {
        if (this == this.belongInnerNode.rightChildrenNode)
            return null;
        if (null == this.belongInnerNode.nextInnerNode)
            return (LeafNode<T>) this.belongInnerNode.rightChildrenNode;
        return (LeafNode<T>) this.belongInnerNode.nextInnerNode.leftChildrenNode;
    }

    protected Iterator<DataNode> iterator() {
        return new Itr();
    }


    private class Itr implements Iterator<DataNode> {
        int size = size();
        DataNode tempData = headDataNode;
        int index = 0;
        @Override
        public boolean hasNext() {
            return index < size;
        }

        @Override
        public DataNode next() {
            DataNode r = tempData;
            tempData = tempData.nextDataNode;
            index++;
            return r;
        }
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer(size() << 2);
        sb.append("(");
        Iterator it = iterator();
        while (it.hasNext())
            sb.append(it.next().toString()).append(", ");
        sb.append(")");
        return sb.toString();
    }

}
